// 队列 + 宽搜
// N叉树/二叉树 的层序遍历：借助一个队列实现
// 层序遍历的方式 结合 堆的思维（用数组存储节点），计算二叉树的宽度

// 例题 3：
// 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
// 树的 最大宽度 是所有层中最大的 宽度 。
// 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
// 将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
//
//        题目数据保证答案将会在  32 位 带符号整数范围内。
//
//        示例 1：
//
//        输入：root = [1,3,2,5,3,null,9]
//        输出：4
//        解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
//        示例 2：
//
//        输入：root = [1,3,2,5,null,null,9,6,null,7]
//        输出：7
//        解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
//        示例 3：
//
//        输入：root = [1,3,2,5]
//        输出：2
//        解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
//
//        提示：
//
//        树中节点的数目范围是 [1, 3000]
//        -100 <= Node.val <= 100

// 解题思路：
// 在层序遍历的基础上，给每一个节点进行编号
// 统计每一层节点的时候，要找到每一层的头结点和尾节点
// 尾节点的编号 - 头节点的编号 + 1 就是二叉树的宽度

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class WidthOfBinaryTree {
    // 解法 1： 层序遍历 + 给每个节点编号
    public int widthOfBinaryTree1(TreeNode root) {
        int ret = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<TreeNode, Integer>(root, 1));
        while(!queue.isEmpty()){
            int size = queue.size();
            int head = 0;
            int tail = 0;
            for(int i = 0; i < size; i++){
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if(i == 0) head = index;
                if(i == size - 1) tail = index;
                if(node.left != null) queue.offer(new Pair<TreeNode, Integer>(node.left, 2 * index));
                if(node.right != null) queue.offer(new Pair<TreeNode, Integer>(node.right, 2 * index + 1));
            }
            if(ret < tail - head + 1) ret = tail - head + 1;
        }
        return ret;
    }
    // 解法 2: 层序遍历 + 使用数组存储二叉树节点（堆的思想）
    public int widthOfBinaryTree2(TreeNode root) {
        List<Pair<TreeNode, Integer>> queue = new ArrayList<>();
        queue.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0;
        while(!queue.isEmpty()){
            ret = Math.max(ret, queue.get(queue.size() - 1).getValue() - queue.get(0).getValue() + 1);
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode, Integer> p : queue){
                TreeNode node = p.getKey();
                int index = p.getValue();
                if(node.left != null) tmp.add(new Pair<TreeNode, Integer>(node.left, 2 * index));
                if(node.right != null) tmp.add(new Pair<TreeNode, Integer>(node.right, 2 * index + 1));
            }
            queue = tmp;
        }
        return ret;
    }
}
